package Point.SlipWindow;

import org.junit.Test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 567 -改写-> 438
 *
 * return ture -> add tmp
 *
 */
public class 找到字符串中所有字母异位词438 {

    public List<Integer> findAnagrams(String s, String need) {
        List<Integer> res = new ArrayList<>();
        Map<Character,Integer> windowMap = new HashMap<>(), needMap = new HashMap<>();
        for(char c : need.toCharArray()) {
            needMap.put(c, needMap.getOrDefault(c, 0)+1);
        }
        for(char c: s.toCharArray()) {
            windowMap.put(c, 0);
        }
        int left=0, right=0, valid=0;

        // r<size
        while (right < s.length()) {
            char c = s.charAt(right);
            right++;
            // 只判断 needSet 的 valid 先+ 后判
            if (needMap.containsKey(c)){
                windowMap.put(c, windowMap.get(c) + 1);
                if(windowMap.get(c).equals(needMap.get(c))){
                    valid++;
                }
            }
            // r-l=ned.len
            while (right - left == need.length()) {
                // if valid = 字母set种类 -> res add
                if (valid == needMap.keySet().size()){
                    res.add(left);
                }
                char d = s.charAt(left);
                left++;
                // [直接粘上面的改]    （ 为什么后-？ ->/**就明白 ）
                if (needMap.containsKey(d)){
                    // x 这里不需要 !反转
                    if(windowMap.get(d).equals(needMap.get(d))){
                        valid--;
                    }
                    windowMap.put(d, windowMap.get(d) - 1);
                }
            }
        }
        return res;
    }


    @Test
    public void test() {
        String s = "cbaebabacd" ,p = "abc";
        System.out.println("RES:" + findAnagrams(s, p));
    }
}
